﻿using System;

namespace SortAndDatastruct {
    /// <summary>
    /// 合并排序[需要额外空间]
    /// 效率：O(NlgN)
    /// </summary>
    class MergeSort : ISort {
        /// <summary>
        /// 实现接口ISort
        /// </summary>
        /// <param name="Array">带排序的数组</param>
        internal override void Sort(ref int[] Array) {
            if (Array == null || Array.Length < 2) return;
            MSort(ref Array, 0, Array.Length - 1);
        }
        /// <summary>
        /// 合并排序的实现是分治思想的代表
        /// </summary>
        /// <param name="Array">带排序的数组</param>
        /// <param name="Left">数组的左端</param>
        /// <param name="Right">数组的右端</param>
        void MSort(ref int[] Array, int Left, int Right) {
            if (Array == null || Array.Length < 2 || Left > Right) return;
            if (Left < Right) {
                int mid = (int)Math.Floor((Left + Right) / 2.0);
                MSort(ref Array, Left, mid);
                MSort(ref Array, mid + 1, Right);
                Merge(ref Array, Left, mid, Right);
            }
        }
        /// <summary>
        /// 合并子数组
        /// </summary>
        /// <param name="Array">带排序的数组</param>
        /// <param name="Left">数组的左端</param>
        /// <param name="Mid">数组的中间</param>
        /// <param name="Right">数组的右端</param>
        void Merge(ref int[] Array, int Left, int Mid, int Right) {
            if (Array == null || Left > Mid || Mid > Right || Left > Right) return;
            int[] subArrayA = new int[Mid - Left + 1];
            int[] subArrayB = new int[Right - Mid];
            for (int i = 0; i < subArrayA.Length; ++i) {
                subArrayA[i] = Array[Left + i];
            }
            for (int i = 0; i < subArrayB.Length; ++i) {
                subArrayB[i] = Array[Mid + 1 + i];
            }
            int j = 0, k = 0;
            while (j < subArrayA.Length && k < subArrayB.Length) {
                if (subArrayA[j] < subArrayB[k]) {
                    Array[Left++] = subArrayA[j++];
                } else {
                    Array[Left++] = subArrayB[k++];
                }
            }
            if (j >= subArrayA.Length) {
                while (k < subArrayB.Length) {
                    Array[Left++] = subArrayB[k++];
                }
            }
            if (k >= subArrayB.Length) {
                while (j < subArrayA.Length) {
                    Array[Left++] = subArrayA[j++];
                }
            }
        }

    }
}
